package ljl.alg.wangzheng_camp.round1.bisection;

/**
 * 两个题型：1. 旋转数组里搜索一个数字 2. 旋转数组，搜索最小值
 * 这是题型 1
 *
 * 这个是可以重复的，更难了
 * 上次那个不能重复的，我都没整明白
 *
 * */
public class _81_search_rotate_array {
    
    class my_wrong_answer {
        /*
         * 1. 左侧升序
         *   1. 看看是不是在左侧
         *   2. 没在，去右侧
         * 2. 右侧升序
         * [1,0,1,1,1] 0
         * */
        public boolean search(int[] nums, int target) {
            int n = nums.length;
            int l = 0, r = n - 1;
            while (l <= r) {
                int mid = (l + r) >>> 1;
                if (nums[mid] == target) return true;
                // 官方题解，用这个判断处理了两个相等夹着一个其它数的情况
                if (nums[mid] == nums[l] && nums[l] == nums[r]) {
                    l++; r--;
                } else if (nums[mid] >= nums[l]) {
                    if (target >= nums[l] && target < nums[mid]) r = mid - 1;
                    else l = mid + 1;
                } else if (nums[mid] <= nums[r]) {
                    if (target > nums[mid] && target <= nums[r]) l = mid + 1;
                    else r = mid - 1;
                }
            }
            return false;
        }
    }
    
    public boolean search(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return true;
            if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
                ++l;
                --r;
            } else if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return false;
    }
    
}
